//环形子数组的最大和
//测试链接：https://leetcode.cn/problems/maximum-sum-circular-subarray/submissions/659637409/
public class MaxSubarraySumCircular {
    public int maxSubarraySumCircular(int[] nums) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int n = nums.length;
        int[] f = new int[n + 1];
        int[] g = new int[n + 1];
        int sum = 0, fmax = Integer.MIN_VALUE, gmin = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            f[i] = Math.max(x, x + f[i - 1]);
            fmax = Math.max(fmax, f[i]);
            g[i] = Math.min(x, x + g[i - 1]);
            gmin = Math.min(gmin, g[i]);
            sum += x;
        }
        return sum == gmin ? fmax : Math.max(fmax, sum - gmin);
    }
}
